﻿#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

//5. 有效三⻆形的个数（medium）
//https://leetcode.cn/problems/valid-triangle-number/description/

//class Solution {
//public:
//    int triangleNumber(vector<int>& nums) 
//    {
//        //排序
//        sort(nums.begin(), nums.end());
//        int ret = 0;
//
//        //先固定最大的数
//        for (int i = nums.size() - 1; i >= 2; i--)
//        {
//            int left = 0, right = i - 1;
//            while (left < right)
//            {
//                //当前左右指针和固定的最大数可以构成三角形
//                //对于前右指针，和区间内的所有值都可以构成三角形，r--
//                if (nums[left] + nums[right] > nums[i])
//                {
//                    ret += right - left;
//                    right--;
//                }
//
//                //当前左右指针和固定的最大数不以构成三角形
//                //对于当前左指针，和区间的数都不能构成三角形,l++
//                else
//                    left++;
//            }
//        }
//        return ret;
//    }
//};

//6. 和为 s 的两个数字（easy）
//https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& price, int target) 
//    {
//        int left = 0, right = price.size() - 1;
//
//        while (left < right)
//        {
//            if (price[left] + price[right] > target)
//                right--;
//            else if (price[left] + price[right] < target)
//                left++;
//            else
//                return { price[left],price[right] };
//        }
//        return { -1,-1 };
//    }
//};
//
//int main()
//{
//    Solution s;
//    vector<int> v({ 3, 9, 12, 15 });
//    s.twoSum(v, 18);
//}


//7. 三数之和（medium）
//https://leetcode.cn/problems/3sum/description/

//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums) 
//    {
//        vector<vector<int>> vv;
//        sort(nums.begin(), nums.end());
//
//        //固定一个数
//        for (int i = 0; i < nums.size() - 2; )
//        {
//            //大于0的数，后面没有两数之和小于0了
//            if (nums[i] > 0)
//                break;
//
//            int left = i + 1, right = nums.size() - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] < -nums[i])
//                {
//                    left++;
//                }
//                else if (nums[left] + nums[right] > -nums[i])
//                {
//                    right--;
//                }
//                else
//                {
//                    vv.push_back({ nums[left],nums[right],nums[i] });
//
//                    int tmpL = nums[left];
//                    while (left < right && nums[left] == tmpL)
//                    {
//                        left++;
//                    }
//                    int tmpR = nums[right];
//                    while (left < right && nums[right] == tmpR)
//                    {
//                        right--;
//                    }
//                }
//            }
//
//            int tmpI = nums[i];
//            while (i < nums.size() - 2 && nums[i] == tmpI)
//            {
//                i++;
//            }
//        }
//        return vv;
//    }
//};


//8. 四数之和（medium）
//https://leetcode.cn/problems/4sum/description/

//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target)
//    {
//        vector<vector<int>> vv;
//        sort(nums.begin(), nums.end());
//
//        int n = nums.size();
//        for (int i = 0; i < n - 3;)
//        {
//            for (int j = i + 1; j < n - 2;)
//            {
//                int left = j + 1, right = n - 1;
//
//                while (left < right)
//                {
//                    long long aim = (long)target - nums[i] - nums[j];
//                    if (nums[left] + nums[right] < aim)
//                        left++;
//                    else if (nums[left] + nums[right] > aim)
//                        right--;
//                    else
//                    {
//                        vv.push_back({ nums[i],nums[j],nums[left++],nums[right--] });
//
//                        while (left < right && nums[left] == nums[left - 1])
//                            left++;
//                        while (left < right && nums[right] == nums[right + 1])
//                            right--;
//                    }
//                }
//
//                j++;
//                while (j < n - 2 && nums[j] == nums[j - 1])
//                    j++;
//            }
//
//            i++;
//            while (i < n - 3 && nums[i] == nums[i - 1])
//                i++;
//        }
//
//        return vv;
//    }
//};
//
//class Solution
//{
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target)
//    {
//        vector<vector<int>> ret;
//        // 1. 排序
//        sort(nums.begin(), nums.end());
//        // 2. 利⽤双指针解决问题
//        int n = nums.size();
//        for (int i = 0; i < n; ) // 固定数 a
//        {
//            // 利⽤ 三数之和
//            for (int j = i + 1; j < n; ) // 固定数 b
//            {
//                // 双指针
//                int left = j + 1, right = n - 1;
//                long long aim = (long long)target - nums[i] - nums[j];
//                while (left < right)
//                {
//                    int sum = nums[left] + nums[right];
//                        if (sum < aim) left++;
//                        else if (sum > aim) right--;
//                        else
//                        {
//                            ret.push_back({ nums[i], nums[j], nums[left++],
//                           nums[right--] });
//                            // 去重⼀
//                            while (left < right && nums[left] == nums[left - 1])
//                                left++;
//                            while (left < right && nums[right] == nums[right + 1])
//                                right--;
//                        }
//                }
//                // 去重⼆
//                j++;
//                while (j < n && nums[j] == nums[j - 1]) j++;
//            }
//            // 去重三
//            i++;
//            while (i < n && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};
//
//
//int main()
//{
//    Solution s;
//    vector<int> v({ 1,0,-1,0,-2,2 });
//    s.fourSum(v, 0);
//
//    return 0;
//}